package com.wyw.leetcode.learning.simple;

import java.util.*;

/**
 * @Title   leetcode topic 653
 * @Description 两数之和 IV - 输入二叉搜索树
 *
 *      给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * Update History:
 * Author        Time            Content
 */
public class Topic653 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(7);

        node.left = node2;
        node.right = node3;

        node3.left=node4;
        node3.right=node5;

        System.out.println(findTarget(node, 11));
    }

    static HashMap<Integer, Integer> hashMap = new HashMap<>();

    public static boolean findTarget(TreeNode root, int k) {
        if(root == null)
            return false;

        if(hashMap.get(root.val) == null) {
            hashMap.put(k - root.val, k - root.val);
        } else
            return true;

        boolean resultL = findTarget(root.left, k);
        if(resultL)
            return true;

        boolean resultR = findTarget(root.right, k);
        if(resultR)
            return true;

        return false;
    }


    /**
     * 哈希表+深度优先
     */
    static Set<Integer> set = new HashSet<>();
    public static boolean findTarget1(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return findTarget1(root.left, k) || findTarget1(root.right, k);
    }


    /**
     * 哈希表+广度优先
     */
    public static boolean findTarget2(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (set.contains(k - node.val)) {
                return true;
            }
            set.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return false;
    }

    /**
     * 深度优先 + 中序遍历 + 双指针
     *
     */
    static List<Integer> list = new ArrayList<>();

    public static boolean findTarget3(TreeNode root, int k) {
        inorderTraversal(root);
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (list.get(left) + list.get(right) == k) {
                return true;
            }
            if (list.get(left) + list.get(right) < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    public static void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        list.add(node.val);
        inorderTraversal(node.right);
    }


    /**
     * 迭代 + 中序 + 双指针
     */
    public static boolean findTarget4(TreeNode root, int k) {
        TreeNode left = root, right = root;
        Deque<TreeNode> leftStack = new ArrayDeque<TreeNode>();
        Deque<TreeNode> rightStack = new ArrayDeque<TreeNode>();
        leftStack.push(left);
        while (left.left != null) {
            leftStack.push(left.left);
            left = left.left;
        }
        rightStack.push(right);
        while (right.right != null) {
            rightStack.push(right.right);
            right = right.right;
        }
        while (left != right) {
            if (left.val + right.val == k) {
                return true;
            }
            if (left.val + right.val < k) {
                left = getLeft(leftStack);
            } else {
                right = getRight(rightStack);
            }
        }
        return false;
    }

    public static TreeNode getLeft(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.right;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        return root;
    }

    public static TreeNode getRight(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.left;
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
        return root;
    }






}
